Nowadays many objects are able to communicate with other objects. That is to say, they are able to send and/or receive information, messages and data. The objects may be permanently installed, stationary or moving. In many situations such as in traffic (e.g. road or air traffic) or in warehouses etc. for example, coordination of such objects (such as vehicles, containers etc.) is useful. It is useful for instance to support safety or management.
In this context, the ability to include the objects in communication networks affords many ways of supporting the aforesaid safety or management. For instance, the objects can at least partially take on the coordination themselves. That is to say, by coordinating with other objects, by receiving position-relevant data and information, the objects can analyze the data and information provided and deduce their positioning in relation to other objects in the vicinity. The objects (hereinafter referred to as nodes) form a network, the purpose of which is to coordinate or position the objects, wherein this is performed at least in part by a corresponding system and/or at least in part by the objects or nodes themselves.
The literature describes various ways of relating the positions of individual nodes and the distances from or between the nodes. It is usually assumed that the network comprises two types of node. Firstly beacon nodes that know their own position, and secondly standard nodes that must calculate their position on the basis of the distances to the beacon nodes.
In terms of their approach, the known methods can be differentiated into non-distance based and distance-based approaches.
In the case of non-distance based approaches, the distance of the individual network nodes is determined using a hop metric (i.e. using the number of other nodes lying between two nodes), and in a further step is converted into geographical distances on the basis of the network topology represented in this way. There is no explicit measurement of the distances between the nodes. These approaches include for example works of the prior art such as Niculescu and Nath [1] as well as, on the basis of the latter, Hsieh and Wang [2].
In the case of distance-based approaches on the other hand, the position of the individual node is estimated with the aid of direct distance measurements between individual network nodes, or between nodes and beacons respectively. Examples of such location-finding methods are, inter alia, [3], [4] and [5]. In [6], an attempt is made to calculate a position estimate with the RSSI (received signal strength indication) of the signals received from the beacon nodes.
Distance-based position determination will be considered below.
The distance is usually calculated using a range or distance calculation method. All in all, a wide variety of methods are used to determine the distance or the range. For instance, measurements can be performed based on the strength of the received signal (received signal strength, RSS), the time of arrival (ToA), the time difference of arrival (TDoA), or roundtrip time of flight (RToF) etc. in order to determine or calculate the range or distance. The problem with all these methods is the inaccuracy of the measurements. That is to say they do not permit any exact range or distance values to be calculated or determined. The result of such measurements is an inexact or estimated range or distance value.
Since distance-based approaches are based on distance specifications, they must be robust in relation to such inexact or estimated range or distance values.
The following two methods for position determination have recently become established among distance-based approaches: multilateration (LSL) [7] and bounding box methods (BB) [5], [8].
FIG. 1a illustrates a method according to the prior art (trilateration) for position determination. In particular FIG. 1a shows how trilateration works when three nodes or neighbors B1, B2, B3 are in the vicinity.
Here the measured distances d1, d2 and d3 from neighboring nodes B1, B2, B3 to the node M to be located are used to estimate the position of M.
Since it is based on a mathematically exact method that does not allow for errors, trilateration is highly prone to errors, both with respect to the positions of the beacon nodes and to the accuracy of the measured distances. As explained above, however, the problem lies in the fact that in practice the measured distances are always estimated and therefore inexact values.
FIG. 1b shows the typical problems encountered when multilateration is used for location-finding. When the range measurements are not perfect and exact, the position is calculated incorrectly. Multilateration is an extended form of trilateration. Whereas trilateration can determine the position of a node with three neighboring nodes, all the available neighboring nodes of the node to be located are used for multilateration.
With multilateration it is possible to estimate the position of the unknown node M from the measured distances d1+derr,1, d2+derr,2 and d3+derr,3 of multiple neighboring nodes P1, P2, P3 to the unknown node M and their known position. Compared with trilateration, multilateration can also handle inexact position or distance measurements. In FIG. 1b the estimated positions Pestim,1, Pestim,2, Pestim,3 deviate from the real positions of the nodes P1, P2, P3. Moreover, the measured distances d1+derr,1, d2+derr,2 and d3+derr,3 contain errors derr,1, derr,2, derr,3. Accordingly, it can be seen from FIG. 1b that the calculated position Mestim deviates from the actual or true position of the node M.
Multilateration has however the disadvantage that it is very prone to error if there is multicollinearity of the neighboring nodes. An error in position determination by means of multilateration is further amplified if there are also errors in the input data (the positions of the neighboring nodes and the corresponding distances). Consequently, even small input errors can cause or produce very large errors in the calculated result position. Another known method is the bounding box method [5], [8] which permits the location-finding of nodes in a network as soon as range measurements can be performed. FIG. 2a shows an example of this method when the measurements are very exact. This method is based on the assumption that the presumed position of a node can be enclosed with the respective measured distances in a rectangular area (the minimum bounding box), the midpoint of which then represents the estimated position. In FIG. 2a the node M to be located has three neighboring nodes P1, P2, P3. Here the enclosing areas or boxes are determined by the positions (x1, y1), (x1, y1), (x1, y1) of the neighboring nodes P1, P2, P3 and the distances d1, d2, d3 of the neighboring nodes to the node M to be located. Mestim is the estimated position of the node M.
The bounding box method provides quite good results if the neighboring nodes lie around the node to be located. Problems arise however when the node to be located has neighbors on one side only (i.e. only on the right, only on the left, or only above, etc.). FIG. 2b illustrates this problem, i.e. the extent of problems the method can have if the user has no neighbors in one direction or on one side (e.g. at the perimeter of the network). In such situations the bounding box method is not able to capture or enclose the node to be located. This results in seriously incorrect estimates of the position of the node to be located. As a consequence, the calculated position Mestim and the actual position of the node M to be located are very far apart.